// 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
// 如果数组中不存在目标值 target，返回 [-1, -1]。
// 进阶：
//     你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？

// 示例 1：
// 输入：nums = [5,7,7,8,8,10], target = 8
// 输出：[3,4]

// 示例 2：
// 输入：nums = [5,7,7,8,8,10], target = 6
// 输出：[-1,-1]

// 示例 3：
// 输入：nums = [], target = 0
// 输出：[-1,-1]
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
let findLeftPosition = function(nums, target) {// [5,7,7,8,8,10]
    let left = 0;
    let right = nums.length - 1;
    let leftBorder = -2;
    while(left <= right) {
        let mid = left + ((right - left) >> 1);
        if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
            leftBorder = right;
        }
    }
    return leftBorder;
}
let findRightPosition = function(nums, target) {
    let left = 0;
    let right = nums.length - 1;
    let rightBorder = -2;
    while(left <= right) {
        let mid = left + ((right - left) >> 1);
        if(nums[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
            rightBorder = left;
        }
    }
    return rightBorder;
}
//////两次二分查找
var searchRange = function(nums, target) {
    if (nums.length === 0) return [-1, -1];
    let leftBorder = findLeftBorder(nums, target);
    let rightBorder = findRightBorder(nums, target);
    if (leftBorder === -2 || rightBorder === -2) {
        return [-1, -1];
    } else if(rightBorder - leftBorder > 1) {
        return [leftBorder + 1, rightBorder - 1];
    }
    return [-1, -1];
};

console.log(searchRange([5,7,7,8,8,10], 8));


